package com.dy.排序.内排序.归并排序;

import java.util.Arrays;
//空间复杂度On，时间复杂度 nlog2n
public class MergingSort {
    //从两个有序数组合并,start到mid，mid+1到end
    public static void merge(int nums[], int tmp[], int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int k = start;
        while (i <= mid && j <= end) {
            if (nums[i] < nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= end) tmp[k++] = nums[j++];
        for (int n = start; n <= end; n++) {
            nums[n ] = tmp[n];
        }
    }

    public static void mergingSort(int[] nums,int tmp[], int left, int right) {

        if (left < right) {
            int mid = (left + right) / 2;
            mergingSort(nums,tmp, left, mid);
            mergingSort(nums,tmp, mid + 1, right);
            merge(nums,tmp, left, mid, right);
        }
    }

    public static void main(String[] args) {
        int nums[] = {3, 2, 4, 1, 2};
        int[] tmp = new int[nums.length];
        mergingSort(nums, tmp,0, nums.length - 1);
        Arrays.stream(nums).forEach(System.out::println);
    }
}
